package leetcode.linkedlist.remove;

import leetcode.linkedlist.ListNode;

/**
 * 82. 删除排序链表中的重复元素 II
 */
public class DeleteDuplicates {


    public static void main(String[] args) {
        DeleteDuplicates solution = new DeleteDuplicates();

        Integer[] arr1 = {4, 2, 1, 3};
        ListNode head = ListNode.makeLinkedList(arr1);

        ListNode newList = solution.deleteDuplicates(head);
        System.out.println(newList.list());
    }

    /**
     * 自己写的 双指针法
     *
     * @param head  链表
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-100, head);
        ListNode pre = dummy;
        ListNode cur = head;
        int count = 1;
        while (cur.next != null) {
            if (cur.next.val == cur.val) {
                cur = cur.next;
                count++;
            } else {
                // 使用 count判断是进行删除还是两个指针同时后移一位
                // 也可以通过 pre.next == cur进行判断
                if (count > 1) {
                    pre.next = cur.next;
                    cur = pre.next;
                    count = 1;
                } else {
                    pre = pre.next;
                    cur = cur.next;
                }
            }
        }
        if (count > 1) {
            pre.next = null;
        }
        return dummy.next;
    }
}
